package 学习计划.数据结构;

/**
 * @author 会玩的洋洋
 * https://leetcode.cn/problems/rotate-image/?envType=study-plan&id=shu-ju-jie-gou-ji-chu&plan=data-structures&plan_progress=cqjfoh6
 */
public class _48_旋转图像 {
    /**
     * 执行用时：0ms，内存消耗：40.1MB
     * 总结规律O(n^2)
     * @param matrix
     */
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        int circle = n >> 1;
        for (int i = 0; i < circle; i++) {
            for (int j = 0; j  < (n + 1) >> 1; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }

    /**
     * 利用额外数组进行赋值
     * 执行时间：0ms，内存消耗：40.1MB
     * @param matrix
     */
    public void rotate2(int[][] matrix) {
        int n = matrix.length;
        int[][] temps = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                temps[i][j] = matrix[n - j - 1][i];
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                matrix[i][j] = temps[i][j];
            }
        }
    }

    /**
     * 顺时针90° = 上下翻转 + 对角线翻转 || 对角线翻转 + 左右翻转
     * 顺时针180° = 上下翻转 + 左右翻转  || 主对角线翻转 + 副对角线翻转
     * 顺时针270° = 左右翻转 + 对角线翻转 // 即逆时针90°
     * 执行用时：0ms，内存消耗：40.1MB
     * @param matrix
     */
    public void rotate3(int[][] matrix) {
        int n = matrix.length;
        // 上下翻转
        for (int i = 0; i < n >> 1; i++) {
            for (int j = 0; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - i - 1][j];
                matrix[n - i - 1][j] = temp;
            }
        }

        // 对角线翻转
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
    }
}
